// @algorithm @lc id=399 lang=cpp 
// @title evaluate-division


#define print(...)
// @test([["a","b"],["b","c"]],[2.0,3.0],[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]])=[6.00000,0.50000,-1.00000,1.00000,-1.00000]
// @test([["a","b"],["b","c"],["bc","cd"]],[1.5,2.5,5.0],[["a","c"],["c","b"],["bc","cd"],["cd","bc"]])=[3.75000,0.40000,5.00000,0.20000]
// @test([["a","b"]],[0.5],[["a","b"],["b","a"],["a","c"],["x","y"]])=[0.50000,2.00000,-1.00000,-1.00000]
// @test([["a","b"],["e","f"],["b","e"]], [3.4,1.4,2.3], [["b","a"],["a","f"],["f","f"],["e","e"],["c","c"],["a","c"],["f","e"]])=[0.29412,10.948,1.0,1.0,-1.0,-1.0,0.71429]
// 并查集
class UnionFind{
    vector<int> direct; // ["a" -> "b"] 有向边, direct[ index("a") ] = index("b")
    vector<double> weight; // "a"->"b" 有向边权重 = a/b
public:
    UnionFind(size_t n) : direct(n,0), weight(n, 1.0){
        for(int i=0; i<direct.size(); i++)
            direct[i] = i;
    }

    int Find(int a){ // 查询：路径压缩
        if(a != direct[a]){
            int parent = direct[a];
            direct[a] = Find(parent);
            weight[a] *= weight[parent];
        }
        return direct[a];
    }

    void Union(int a, int b, double w){
        int aParent = Find(a);
        int bParent = Find(b);
        if(aParent == bParent) return;
        direct[aParent] = bParent;
        weight[aParent] = w * weight[b] / weight[a];
    }

    double IsConnected(int a, int b){
        int aParent = Find(a);
        int bParent = Find(b);
        if(aParent == bParent) // true
            return weight[a] / weight[b];
        return -1.0; // false
    }
};
class Solution {
    unordered_map<string, int> index;
public:
    vector<double> calcEquation(vector<vector<string>>& equations,
                    vector<double>& values,
                    vector<vector<string>>& queries)
    {
        int n = equations.size();
        UnionFind uf(n*2);
        for(int i=0,h=0; i<n; i++){
            auto & v = equations[i];
            if(!index.count(v[0])) index[ v[0] ] = h++;
            if(!index.count(v[1])) index[ v[1] ] = h++;
            uf.Union( index[v[0]], index[v[1]], values[i] );
        }
        print("index=", index, "\n");

        int m = queries.size();
        vector<double> ans(m, -1.0);
        for(int i=0; i<m; i++){
            auto & v = queries[i];
            auto ia = index.find(v[0]);
            if(ia==index.end()) continue;
            auto ib = index.find(v[1]);
            if(ib==index.end()) continue;
            ans[i] = uf.IsConnected(ia->second, ib->second);
        }
        return ans;
    }
};